1. Field of the Invention
The present invention relates generally to a turbo encoder for a radio communication system, and in particular, to an interleaver for a turbo encoder in an UMTS (Universal Mobile Telecommunication System) and a method for performing interleaving.
2. Description of the Related Art
In general, a turbo encoder using a turbo code is typically used for a radio communication system such as ISDN (Integrated Services Digital Network), digital cellular, W-CDMA (Wideband Code Division Multiple Access) and IMT-2000 systems. The turbo encoder includes an interleaver, which improves a codeword distance characteristic by randomizing data input to the turbo encoder. A performance of the turbo encoder chiefly depends on the interleaver.
FIG. 1 illustrates a structure of a conventional turbo encoder designated generally by reference numeral 106. As illustrated, the turbo encoder 106 includes a first constituent encoder 102 for encoding input frame data dK into output data Y1K, an interleaver 100 for interleaving the input fame data dK, and a second constituent encoder 104 for encoding the interleaved data output from the interleaver 100 into output data Y2K. As a result, the turbo encoder 106 outputs data XK equivalent to the non-encoded input fame data dK, the encoded data Y1K and the interleaved encoded data Y2K. the interleaver 100 outputs data, which is equal in size to the input data frame dK, and permutes the sequence of the data bits input to the second constituent encoded 104 so as to reduce correlation among the data bits.
A detailed description of the interleaver 100 will now be given below. The interleaver 100 sequentially stores the input data in a memory with a matrix structure of rows and columns, and then initializes interleaving parameters determined according to the number of input data bits. That is, the interleaver 100 sets various parameters such as index of row number of rectangular matrix j and index of column number of rectangular matrix i and prime number p and primitive root μ for inter-row/intra-row permutation for interleaving the input data as well as the number R of the rows and the number C of the columns, to the values corresponding to the number K of the input data bits by consulting a table in the memory.
For example, if the number of the input data bits is K=40, then the parameters are determined as R=5, C=8, p=7 and μ=3. The interleaver 100 then arranges the input data in a 5×8 matrix of the memory as shown in Table 1 below.
TABLE 112345678910111213141516171819202122232425262728293031323334353637383940
Subsequently, the interleaver 100 first performs interleaving on the rows of the input data, arranged as shown in Table 1. At this point, the interleaver 100 determines an iter-row permutation pattern T(j) to perform interleaving on the rows. The inter-row permutation pattern T(j) is a function for inter-row interleaving the input data, and is determined by Equation (1) below according to the number K of the input data bits.T(j)=pat4 (for 40≦K≦159)  Equation (1)T(j)=pat3 (for 160≦K≦200)T(j)=pat1 (for 201≦K≦480)T(j)=pat3 (for 481≦K≦5530)T(j)=pat1 (for 531≦K≦2280)T(j)=pat2 (for 2281≦K≦2480)T(j)=pat1 (for 2481≦K≦3160)T(j)=pat2 (for 3161≦K≦3210)T(j)=pat1 (for 3211≦K≦5114)    where pat1={19,9,14,4,0,2,5,7,12,18,10,8,13,17,3,1,16,6,15,11},     pat2={19,9,14,4,0,2,5,7,12,18,16,13,17,15,3,1,6,11,8,10},     pat3={9,8,7,6,5,4,3,2,1,0}, and     pat4={4,3,2,1,0}.
The interleaver 100 permutes the rows of the input data by coping a T(j)th row of the original matrix into a jth row of a new matrix according to the inter-row permutation pattern T(j). That is, since the number of the input data bits is K=40, the inter-row permutation pattern is determined as T(j)=pat4. Table 2 below shows a matrix of the input data which was subjected to inter-row permutation according to the selected permutation sequence. As shown in Table 2, the 4th row's data of the original matrix is rearranged in the 0th row of the new matrix; the 3rd row's data of the original matrix is rearranged in the 1st row of the new matrix; the 2nd row's data of the original matrix is rearranged in the 2nd row of the new matrix; the 1st row's data of the original matrix is rearranged in the 3rd row of the new matrix; and the 0th row's data of the original matrix is rearranged in the 4th row of the new matrix.
TABLE 233343536373839402526272829303132171819202122232491011121314151612345678
Thereafter, the interleaver 100 sequentially calculates a minimum prime integer sequence q(j), a permuted prime integer sequence r(j), and intra-row permutation basic sequence s(i), which are permutation sequences for intra-row permutation, in accordance with Equation (2) below.g.c.d{q(j),p−1 }=1,q(j)>6,q(j) >q(j−1),q=1,2, . . . ,R−1,q(0)=1 (where g.c.d is greatest common divisor)  Equation 2r[T(j)]=q(j),j=0,1, . . . ,R−1s(i)=[μ×s(i−1)] modp,i=1,2, . . . ,(p−2),s(0)=1
Further, the interleaver 100 calculates a final intra-row permutation pattern Ui(j) for the inter-row/intra-row permutation using the intra-row permutation basic sequence s(i), in accordance with Equation (3) below.1. Uj(i)=s{[i×r(j)] mod(p−1)},i=0,1,2, . . . ,p−2,U(p−1)=0(for C=p)  Equation (3)2. Uj(i)=s{[i×r(j)] mod(p−1)},i=0,1,2, . . . ,p−2,U(p−1)=0,U(p)=p(for C=p+1).When K=C×R, UR−1(p) is exchanged with UR−1(0) after intra-row permutation.3. Uj(i)=s{[i×r(j)] mod(p−1)}−1,i=0,1,2, . . . ,p−2(for C=p)
That is, for the respective columns, the final intra-row permutation pattern values Uj(i) are calculated as shown in Equation(4) below.U0(i)=s(17i mod 6)={s(0),s(5),s(4), s(3),s(2),s(1),0,7}={1,5,4,6,2,3,0,7}  Equation (4)U1(i)=s(13i mod 6)={s(0),s(1),s(2),s(3),s(4),s(5),0,7}={1,3,2,6,4,5,0,7}U2(i)=s(11i mod 6)={s(0),s(5),s(4),s(3),s(2),s(1),0,7}={1,5,4,6,2,3,0,7}U3(i)=s(7i mod 6)={s(0),s(1),s(2),s(3),s(4),s(5),0,7}={1,3,2,6,4,5,0,7}U4(i)=s(i mod 6)={7,s(1),s(2),s(3),s(4),s(5),0,s(0)}={7,3,2,6,4,5,0,1}
Therefore, the interleaver 100 performs the final interleaving as shown in Table 3 below by intra-row permuting the data sequence which was subjected to inter-row permutation as shown in Table 2, according to the final intra-row permutation pattern Uj(i) for the intra-row permutation.
TABLE 334363734353633402628273129302532182221231920172410121115131491684375612
As described above, the interleaver 100 of the conventional turbo encoder 106 requires an additional temporary memory to intermediately (or temporarily) store the permuted data in the process of interleaving the input data, which can overload a microprocessor and/or a digital signal processor (DSP).